package com.sali.Tree;


import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author sali
 * @date 2025/5/5 16:02
 */
public class LeetCode_272 {

    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        List<Integer> res = new ArrayList<>();

        PriorityQueue<Integer> myQue = new PriorityQueue<>(
                (o1,o2) -> Double.compare(Math.abs(o2 - target), Math.abs(o1 - target))
        );

        getRes(root, target, k, myQue);

        List<Integer> myList = new ArrayList<>(myQue);
        res.addAll(myList);

        return res;
    }

    private void getRes(TreeNode root, double target, int k, PriorityQueue<Integer> myQue) {
        if ( root == null ) {
            return;
        }

        getRes(root.left, target, k, myQue);

        if ( myQue.size() < k ) {
            myQue.offer(root.val);
        } else {
            int curVal = myQue.peek();
            if ( Math.abs(curVal - target) > Math.abs(root.val - target) ) {
                myQue.poll();
                myQue.offer(root.val);
            }
        }

        getRes(root.right, target, k, myQue);
    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}
